Finding the Next Open Slot

Tombstones


개방주소에서 삭제한 칸을 처음부터 빈 칸과 같은 모양으로 두면, 충돌로 뒤에 밀린 키를 찾는 조사 경로가 중간에서 끊긴다. tombstone은 지운 칸을 나타내는 표시로, 탐색에는 지나갈 칸으로, 삽입에는 다시 쓸 수 있는 칸으로 쓰인다.

처음부터 빈 칸이 뒤에는 같은 경로로 저장된 키가 없다는 뜻이다.
tombstone삭제 흔적이며 탐색은 지나가고 삽입은 후보 위치로 기억한다.
재할당활성 항목만 새 표에 다시 넣어 tombstone을 정리한다.

지운 칸을 빈 칸으로 두면 뒤에 밀린 키를 찾지 못한다

삭제 처리 방식과 찾을 키를 바꾸면 44를 지운 표에서 조사 경로, 멈춘 이유, 탐색 결과가 바뀐다. 77, 44, 55는 h(k) = 0, 31과 20은 h(k) = 9, 54는 h(k) = 10이다.

칸 위 숫자는 인덱스다. 회색 점선 칸은 tombstone, 파란 칸은 지나간 칸, 초록 테두리 칸은 찾은 칸, 빨간 칸은 탐색이 멈춘 빈 칸이다.

삽입은 처음 만난 tombstone을 기억했다가 키가 없으면 그 자리에 넣는다

넣을 키를 바꾸면 tombstone이 있는 표에서 같은 키가 있는지 끝까지 확인한 경로와 실제로 저장하거나 갱신하는 칸이 바뀐다.

칸 위 숫자는 인덱스다. 파란 칸은 확인한 칸, 초록 테두리 칸은 최종으로 쓰는 칸이며, 회색 점선 칸은 tombstone이다.